package main.sort;

public class HeapSort extends BaseSort {
    public HeapSort(int[] array) {
        super(array);
        this.name = "堆排序";
    }

    /**
     * 先建立堆，每次取最大值放最后
     * <br>
     * [7, 5, 6, 1, 4, 3, 2, 8]<br>
     * [6, 5, 3, 1, 4, 2, 7, 8]<br>
     * [5, 4, 3, 1, 2, 6, 7, 8]<br>
     * [4, 2, 3, 1, 5, 6, 7, 8]<br>
     * [3, 2, 1, 4, 5, 6, 7, 8]<br>
     * [2, 1, 3, 4, 5, 6, 7, 8]<br>
     * [1, 2, 3, 4, 5, 6, 7, 8]
     */
    @Override
    public void sort() {
        int len = array.length;
        heapBuilder(array, len);
        for (int i = len - 1; i > 0; i--) {
            swap(array, 0, i);
            fixDown(array, 0, --len);
            print();
        }
    }

    public void heapBuilder(int[] arr, int len) {
        for (int i = len >> 1; i >= 0; i--) {
            fixDown(arr, i, len);
        }
    }

    public void fixDown(int[] arr, int i, int len) {
        int left = (i << 1) + 1;
        int right = (i << 1) + 2;
        int largest = i;
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            fixDown(arr, largest, len);
        }
    }
}
